AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents

摘要

A satisfactory multiagent learning algorithm should, {\em at a minimum},learn to play optimally against stationary opponents and converge to a Nashequilibrium in self-play. The algorithm that has come closest, WoLF-IGA, hasbeen proven to have these two properties in 2-player 2-action repeatedgames--assuming that the opponent's (mixed) strategy is observable. In thispaper we present AWESOME, the first algorithm that is guaranteed to have thesetwo properties in {\em all} repeated (finite) games. It requires only that theother players' actual actions (not their strategies) can be observed at eachstep. It also learns to play optimally against opponents that {\em eventuallybecome} stationary. The basic idea behind AWESOME ({\em Adapt When Everybody isStationary, Otherwise Move to Equilibrium}) is to try to adapt to the others'strategies when they appear stationary, but otherwise to retreat to aprecomputed equilibrium strategy. The techniques used to prove the propertiesof AWESOME are fundamentally different from those used for previous algorithms,and may help in analyzing other multiagent learning algorithms also.